import com.yusong.algorithm.data.DataConstants;

import java.util.*;

/**
 * 1.找出所有的0
 * 2.计算每个非0元素需要移动的位置
 * 3.结尾补充0
 */
public class Main {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Main main = new Main();
        //int[] grid = {-1, 0, 1, 2, -1, -4};
        //int[] grid = {3,0,-2,-1,1,2};
        int[] grid = {0,0,0,0};

        int[] A = {1, 2};
        int[] B = {-2,-1};
        int[] C = {-1, 2};
        int[] D = { 0, 2};

        int[][] points = {{0,0},{1,0},{2,0}};
        //[]

        int[] nums ={
                -2147483648,-2147483647};

        main.containsNearbyAlmostDuplicate(nums, 3, 3);
        long duration = System.currentTimeMillis() - start;
        System.out.println(duration);
    }


    /**
     * 滑动窗口解决
     * 红黑树
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int length = nums.length;
        if(length == 0 || k ==0){
            return false;
        }
        TreeSet<Integer> orderCache = new TreeSet<>();
        orderCache.add(nums[0]);
        for(int index = 1; index < length; index++){
            Integer currentNumber = nums[index];
            Integer floor = orderCache.floor(currentNumber);
            if(floor != null && (long)floor >= ((long)currentNumber - t)){
                return true;
            }

            Integer ceiling = orderCache.ceiling(currentNumber);
            if(ceiling != null && (long)ceiling <=( (long)currentNumber + t)){
                return true;
            }

            orderCache.add(currentNumber);
            if(index >= k){
                Integer firstNumber = nums[index -k];
                orderCache.remove(firstNumber);
            }
        }

        return false;
    }






}